#include <stdio.h>
#include <stdbool.h>
#include <string.h>
#include <stdlib.h>

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* intersection(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) {
    int ans[1001] = {0};
    for (int i = 0; i < nums1Size; i++)
        ans[nums1[i]] = 1;

    for (int i = 0; i < nums2Size; i++)
        if (ans[nums2[i]] == 1)
            ans[nums2[i]] = 2;
    
    int cnt = 0;
    for (int i = 0; i < 1001; i++)
        if (ans[i] == 2)
            cnt ++;
    int *retans = (int *)malloc(cnt * sizeof(int));
    memset(retans, 0, cnt * sizeof(int));
    *returnSize = cnt;

    for (int i = 0, j = 0; i < 1001; i++)
        if (ans[i] == 2)
            retans[j++] = i;
    return retans;
}

int main(void)
{
    printf("#349. 两个数组的交集\n");

    printf("\n这道题是简单题，但是还是很有必要拿出来说说：\n");
    printf("\n首先看到它时，知道是哈希题，想着用c语言做不了，用python的dict做。其实错了\n");
    printf("简单的哈希，我们可以完全临时用数组构造一个哈希表，用一个很简单的哈希值计算方法去数组索引。\n");

    printf("\n 比如这个题，\n    题目说明的nums成员不会大于1000,则直接定义一个长度为1001的数组，拿nums的数值作为索引。然后遍历2个数组，找到交集的元素\n");

    int nums1[] = {1,2,2,1};
    int nums2[] = {2,2};

    int cnt = 0;
    int *ret = intersection(nums1, sizeof(nums1)/sizeof(int), nums2, sizeof(nums2)/sizeof(int), &cnt);

    for (int i = 0; i < cnt; i++) {
        printf("%d ", ret[i]);
    }
    printf("\n");
    return 0;
}